package java.util.concurrent.locks;

import sun.misc.Unsafe;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Date;
import java.util.concurrent.TimeUnit;

//他是一个同步工具，也是Lock用来实现线程同步的核心组件。
//两个功能：
//1.独占模式：每次只有一个线程持有锁
//2.共享锁：允许多线程同时获取锁，并发访问共享资源
//AQS队列内部维护的是一个FIFO的双向链表，这种结构的特点是每个数据结构都有两个指针，
//分别指向直接的后继节点和直接的前驱结点。所以双向链表可以从任意一个结点开始很方便的访问前驱和后继。
//每个Node其实是由线程封装，当线程争抢锁失败后会封装成Node加入到AQS队列中去，
//当获取锁的线程释放锁之后，会从队列中唤醒一个阻塞的节点（线程）。
public abstract class AbstractQueuedLongSynchronizer
        extends AbstractOwnableSynchronizer
        implements java.io.Serializable {

    private static final long serialVersionUID = 7373984972572414692L;

    // Queuing utilities

    static final long spinForTimeoutThreshold = 1000L;


    //jdk层面的unsafe实例
    private static final Unsafe unsafe = Unsafe.getUnsafe();
    //锁状态偏移量
    private static final long stateOffset;
    //头节点偏移量
    private static final long headOffset;
    //尾结点的偏移量
    private static final long tailOffset;
    //节点状态偏移量
    private static final long waitStatusOffset;
    //下一个节点的偏移量
    private static final long nextOffset;

    static {
        try {
            stateOffset = unsafe.objectFieldOffset
                    (AbstractQueuedLongSynchronizer.class.getDeclaredField("state"));
            headOffset = unsafe.objectFieldOffset
                    (AbstractQueuedLongSynchronizer.class.getDeclaredField("head"));
            tailOffset = unsafe.objectFieldOffset
                    (AbstractQueuedLongSynchronizer.class.getDeclaredField("tail"));
            waitStatusOffset = unsafe.objectFieldOffset
                    (Node.class.getDeclaredField("waitStatus"));
            nextOffset = unsafe.objectFieldOffset
                    (Node.class.getDeclaredField("next"));

        } catch (Exception ex) {
            throw new Error(ex);
        }
    }

    protected AbstractQueuedLongSynchronizer() {
    }

    static final class Node {

        //枚举
        //共享模式
        static final Node SHARED = new Node();
        //独占模式
        static final Node EXCLUSIVE = null;


        //表示当前节点处于取消状态，会被队列中的后置节点移除出去
        static final int CANCELLED = 1;
        //表示当前节点需要唤醒他的后继节点，他表示的其实是后继节点的状态，需要当前节点去个呼叫他
        static final int SIGNAL = -1;

        //共享模式相关的东西
        //condition相关的东西
        static final int CONDITION = -2;
        static final int PROPAGATE = -3;

        //当前的节点状态  ，默认 ==0， >0表示取消状态，==-1 表示当前node如果是head节点时，释放锁之后需要唤醒后继节点
        volatile int waitStatus;
        //FIFO队列的指针
        //前驱节点
        volatile Node prev;
        //后继节点
        volatile Node next;
        //当前节点封装的线程
        volatile Thread thread;
        //存储在condition队列的后继节点，
        Node nextWaiter;


        //是否为共享锁
        final boolean isShared() {
            return nextWaiter == SHARED;
        }

        //获取当前节点的当前节点
        final Node predecessor() throws NullPointerException {
            Node p = prev;
            if (p == null)
                throw new NullPointerException();
            else
                return p;
        }

        Node() {
        }

        Node(Thread thread, Node mode) {     // Used by addWaiter
            this.nextWaiter = mode;
            this.thread = thread;
        }

        Node(Thread thread, int waitStatus) { // Used by Condition
            this.waitStatus = waitStatus;
            this.thread = thread;
        }
    }

    //头节点，任何时刻，头节点对应的线程都是当前持有锁的线程
    private transient volatile Node head;
    //尾结点，阻塞队列的尾结点（严格来说，其实阻塞队列不包含头节点，因为头结点的线程持有锁）
    private transient volatile Node tail;
    //状态字段，这个状态其实类似于资源
    //独占模式下 0 表示未加锁状态  > 0 表示加锁状态
    //共享模式下
    //独占模式也好，共享模式也好，只有获得资源的线程，才能继续往下执行业务逻辑。
    private volatile long state;

    //ps：父类还有一个属性 AbstractOwnableSynchronizer

    //获取state的值
    protected final long getState() {
        return state;
    }

    //设置state字段的值，注意这里是线程不安全的。
    protected final void setState(long newState) {
        state = newState;
    }

    //cas的方式去更新state的值，线程安全的，但是效率没有上面的方法高。
    protected final boolean compareAndSetState(long expect, long update) {
        return unsafe.compareAndSwapLong(this, stateOffset, expect, update);
    }

    //线程安全的方式去修改头节点
    private final boolean compareAndSetHead(Node update) {
        return unsafe.compareAndSwapObject(this, headOffset, null, update);
    }

    //线程安全的去设置尾结点
    private final boolean compareAndSetTail(Node expect, Node update) {
        return unsafe.compareAndSwapObject(this, tailOffset, expect, update);
    }

    //线程安全的方式去设置节点状态
    private static final boolean compareAndSetWaitStatus(Node node,
                                                         int expect,
                                                         int update) {
        return unsafe.compareAndSwapInt(node, waitStatusOffset,
                expect, update);
    }

    //线程安全的去设置下一个节点
    private static final boolean compareAndSetNext(Node node,
                                                   Node expect,
                                                   Node update) {
        return unsafe.compareAndSwapObject(node, nextOffset, expect, update);
    }


    //设置头节点为当前节点
    //这里为什么不用锁呢？
    //因为设置头节点的线程是当前持有锁的线程，独占模式下，只有一个线程持有锁，所以设置头节点不存在线程安全问题
    private void setHead(Node node) {
        head = node;
        node.thread = null;
        node.prev = null;
    }

    public String toString() {
        long s = getState();
        String q = hasQueuedThreads() ? "non" : "";
        return super.toString() +
                "[State = " + s + ", " + q + "empty queue]";
    }

    //==================================以下为独占锁的主要逻辑==========================================//

    public final void acquire(long arg) {
        //tryAcquire方法尝试获取锁，成功返回true，失败返回false。
        //如果尝试获取锁失败，那就通过addWaiter将当前线程封装成node节点加入到链表，
        //在通过acquireQueued方法去竞争锁；注意这个方法返回的是，
        //当前线程在入队过程中有没有其他线程给自己设置了响应中断信号，也就是将当前线程的中断标识位设置成true。
        if (!tryAcquire(arg) &&
                acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
            //什么时候执行这里呢?
            //如果当前线程尝试获取锁失败 && 当前线程被封装成node节点入队成功，且竞争锁成功
            //就会走响应中断的逻辑
            //表示当前线程在入队过程中被中断过，则需要产生一个中断请求，
            //因为线程在进行入队过程中，是不会响应中断请求的。
            selfInterrupt();
    }

    //执行中断逻辑
    static void selfInterrupt() {

        //回顾一下基础知识：
        //1. interrupt() ：其他线程调用当前线程的interrupt()方法，表示当前线程可以优雅的中断退出了，至于什么时候中断，取决于当前线程自己。
        //2. Thread.currentThread().isInterrupted()： 线程检查自身是否被其他线程中断过。
        //3. Thread.interrupted() : 对设置中断标识的线程进行复位。举个例子：其他线程通过方法1将当前线程设置了中断标识，但是当前线程不想中断
        // 可以通过静态方法 Thread.interrupted() 将中断标识复位，假装没有人给他设置过中断标识。
        //额外补充一点：还有一种可以将当前线程中断标识位复位的方法，那就是抛出响应中断异常。

        //这个其实就是当前线程自己调用了方法1，将自己的中断标识设置成true。
        Thread.currentThread().interrupt();
    }

    //将当前线程封装成Node节点
    private Node addWaiter(Node mode/*Node.EXCLUSIVE：表示是独占模式。*/) {
        //构建一个节点
        Node node = new Node(Thread.currentThread(), mode);
        // Try the fast path of enq; backup to full enq on failure
        //获取到尾结点
        Node pred = tail;
        //判断尾节点是否为空
        if (pred != null) { //条件成立：说明尾节点不为空，也就是阻塞队列已经有其他线程封装的节点了，这个时候我们尝试去吧当前节点设置成新的尾结点
            //将当前节点的前驱指针指向尾结点
            node.prev = pred;
            //cas操作把当前的节点设置成尾结点
            if (compareAndSetTail(pred, node)) {
                //来到这里说明cas成功了，
                //完善链表即可
                pred.next = node;
                //返回当前节点
                return node;
            }
        }
        //来到这里是什么情况呢？
        //1.尾结点为空，说明队列尚未初始化
        //2.当前节点cas的方式加入队尾失败，说明有其他线程先一步入队了
        enq(node);
        return node;
    }

    //自旋的方式把当前节点加入到队列中
    private Node enq(final Node node) {
        for (; ; ) {
            Node t = tail;
            //尾结点为空，说明当前队列尚未初始化
            if (t == null) { // Must initialize
                if (compareAndSetHead(new Node()))
                    tail = head;
                //注意，这里初始化完并没有直接break出去，会继续新的一轮循环，为什么呢？
                //因为当前执行的是初始化操作，那就说明，当前这个抢占锁失败的线程需要给当前持有锁的线程补充一个头节点
            } else {
                //来到这里说明尾结点不为空

                node.prev = t;
                //cas的方式去设置尾结点
                if (compareAndSetTail(t, node)) {
                    //让尾结点的后继指针指向当前节点
                    t.next = node;
                    return t;
                }
            }
        }
    }

    //把当前线程封装的节点作为参数传递过来，去竞争锁
    final boolean acquireQueued(final Node node, long arg) {
        //表示当前线程获取锁是否发生了异常
        //这个标识其实是响应中断获取锁的时候用到的
        boolean failed = true;
        try {
            //当前线程在入队过程中是否被其他线程设置过响应中断信号，默认是false，表示没有。
            boolean interrupted = false;
            for (; ; ) {
                //获取当前节点的前驱节点
                final Node p = node.predecessor();
                //前驱节点是头节点，也就是当前持有锁的节点 ，说明当前节点拥有了竞争锁的权利，尝试用cas的方式去获取锁。
                if (p == head && tryAcquire(arg)) {

                    //什么时候走到这里？
                    //当前节点的前驱节点是头节点 && 当前节点cas获取锁成功！

                    //设置头节点为当前节点
                    setHead(node);
                    //将原头节点出队，help gc
                    p.next = null; // help GC
                    //声明获取锁成功
                    failed = false;
                    //返回当前线程不需要被中断
                    return interrupted;
                }
                //当前节点的前驱节点不是头节点 || cas的方式获取锁失败了
                //走到这里说明当前持有锁的线程可能尚未释放锁，所以当前线程尝试获取锁会失败，这个时候当前线程应该park。
                if (shouldParkAfterFailedAcquire(p, node) &&  //这个方法什么时候返回true？ 前驱节点是SIGNAL状态。
                        parkAndCheckInterrupt())  //这个方法什么时候返回true？当前线程在入队过程中被其他线程设置了响应中断信号。
                    //这里比较友好，仅仅是吧中断标识改成了true，如果是响应中断逻辑，直接这里就抛异常了，然后走cancelAcquire的逻辑。
                    interrupted = true;
                //这里其实是什么意思呢？
                //首先聊一下LockSupport.park();和thread.interrupt()他俩一点有趣的事儿....
                //在jvm源码里面:interrupt0()这个方法，直接调用了Thread::interrupt(thr)，
                //而Thread::interrupt(thr) 实际上调用了os::interrupt()，这个是调用平台的 interrupt()
                //以 os_linux.cpp 文件为例：set_interrupted(true)实际上就是调用 osThread.hpp 中的set_interrupted()
                //总结来说：thread.interrupt()实际就是设置一个 interrupted 状态标识为 true、并且通过ParkEvent 的 unpark()来唤醒线程。
                // head  -> current  -> node -> node -> tail
                //head节点释放锁了，这个时候，唤醒了 head.next 也就是当前线程所在节点 current
                //注意这个时候current处于parkAndCheckInterrupt()方法内呢，他醒了之后，如果获取到了锁，继续往下执行....
                //return Thread.interrupted();  返回当前线程是否被其他线程设置过中断信号
                //接下来进行新的一轮自旋....
            }
        } finally {
            //如果获取锁的过程中出现了异常
            if (failed)
                //取消竞争锁的逻辑
                cancelAcquire(node);
        }
    }

    //当前线程抢占锁失败以后的park逻辑
    //这个是什么场景呢？
    //线程A还没有释放锁，线程b和线程c来争抢锁肯定会失败的，那么失败以后就会走这里的逻辑。
    // head -> node1 -> node2
    //  A       B        C
    private static boolean shouldParkAfterFailedAcquire(Node pred/*当前线程所在节点的前驱节点*/, Node node/*当前线程所在的节点*/) {
        //前驱节点的等待状态
        int ws = pred.waitStatus;

        //表示当前节点需要唤醒他的后继节点，他表示的其实是后继节点的状态，需要当前节点去个呼叫他

        //SIGNAL:如果前驱节点为SIGNAL，意味着只需要等待其前置节点的线程被释放
        if (ws == Node.SIGNAL)

            return true;
        //前驱节点的状态大于0，意味着前驱节点取消了排队，直接移除这个节点就行。
        if (ws > 0) {

            do {
                //相当于 pred = pred.prev ; node.prev = pred ;
                node.prev = pred = pred.prev;
            } while (pred.waitStatus > 0); //这里采用循环从双向链表移除了取消状态的节点
            pred.next = node;
        } else {
            //来到这里说明前驱节点不是取消状态也不是SIGNAL
            //利用cas设置前驱节点的状态为 SIGNAL
            compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
        }
        return false;
    }

    private final boolean parkAndCheckInterrupt() {
        //挂起当前线程变成waiting状态
        LockSupport.park(this);

        //这个线程重新支棱起来有两种情况：
        //1.其他线程调用了它的 thread.interrupt();
        //2.他是头节点的下一个节点，头节点出队的时候把他唤醒了.....

        //返回当前线程是否被其他线程触发过中断请求，也就是 thread.interrupt();
        //如果有触发过中断请求，那么这个方法会返回当前的中断标识true，并且对中断标识进行复位，
        //表示已经响应过了中断请求。如果返回true，意味着在acquire方法中会执行 selfInterrupt() 。
        return Thread.interrupted();
    }

    // Utilities for various versions of acquire
    //取消抢锁的逻辑
    private void cancelAcquire(Node node) {
        // 如果节点不存在，直接返回。
        if (node == null)
            return;
        //将当前节点的线程设置为空
        node.thread = null;
        //获取当前节点的前驱节点
        // Skip cancelled predecessors
        Node pred = node.prev;
        //循环判断:如果前驱节点为空，那就继续往前找
        while (pred.waitStatus > 0)
            node.prev = pred = pred.prev;

        //可能是当前节点，也可能是 waitStatus>0的节点
        Node predNext = pred.next;

        //设置当前节点的waitStatus是取消状态
        node.waitStatus = Node.CANCELLED;


        //当前取消排队的节点所在队列的位置不同，执行的出队策略是不一样的，大概分三种情况讨论：
        //1.当前node处于队尾
        //2.当前node不是head.next,也不是tail
        //3.当前节点是head.next节点

        //情况一：当前节点是尾结点，且cas设置前驱节点为尾结点成功
        if (node == tail && compareAndSetTail(node, pred)) {
            //pred.next = null -> 尾结点出队逻辑
            compareAndSetNext(pred, predNext, null);
        } else {

            //情况二：当前节点不是head.neext节点，也不是尾结点
            int ws;

            if (    //当前节点不是头节点的下一个节点
                    pred != head &&
                            //当前节点的前驱节点是取消状态 || 前驱节点的状态小于0 ，并且cas设置前驱节点的状态为SIGNAL成功，表示要唤醒后继节点
                            ((ws = pred.waitStatus) == Node.SIGNAL ||
                                    (ws <= 0 && compareAndSetWaitStatus(pred, ws, Node.SIGNAL))) &&
                            //前驱节点的线程不为空
                            pred.thread != null) {
                //条件成立：来到这里之后，其实就是让当前节点的前驱指针跨过当前节点直接指向当前节点的next节点。
                Node next = node.next;
                if (next != null && next.waitStatus <= 0)
                    compareAndSetNext(pred, predNext, next);
            } else {
                //情况三：当前节点是头节点的下一个节点 && 当前节点不是尾结点
                //那就跨过当前节点
                // head.next = node.next
                // node.next.prev = head
                unparkSuccessor(node);
            }

            node.next = node; // help GC
        }
    }

    //唤醒当前节点
    private void unparkSuccessor(Node node) {
        //获取节点的状态
        int ws = node.waitStatus;
        //如果节点状态小于0 SIGNAL -1 等待被唤醒
        if (ws < 0)
            //修改节点的状态为0
            compareAndSetWaitStatus(node, ws, 0);


        //获取当前节点的下一个节点
        Node s = node.next;
        //如果下一个节点为null || 下一个节点的状态>0，表示取消状态
        if (s == null || s.waitStatus > 0) {
            s = null;
            //从链表尾节点开始扫描，找到距离当前节点最近的一个状态<=0 的节点
            for (Node t = tail; t != null && t != node; t = t.prev)
                if (t.waitStatus <= 0)
                    s = t;
        }
        //唤醒这个节点
        if (s != null)
            LockSupport.unpark(s.thread);

        // head  -> cancel -> cancel - signal -> tail

    }

    //释放锁的逻辑
    public final boolean release(long arg) {
        //如果尝试释放锁成功
        if (tryRelease(arg)) {
            Node h = head;
            //如果头结点不为空 && 头节点状态 ！= 0
            if (h != null && h.waitStatus != 0)
                //唤醒后继线程
                unparkSuccessor(h);
            return true;
        }
        return false;
    }


    public final void acquireInterruptibly(long arg)
            throws InterruptedException {
        //如果当前线程被设置了中断信号，抛出响应中断异常
        if (Thread.interrupted())
            throw new InterruptedException();
        //如果当前线程尝试获取锁失败
        if (!tryAcquire(arg))
            //走响应中断获取锁的逻辑
            doAcquireInterruptibly(arg);
    }


    //响应中断获取锁的逻辑
    private void doAcquireInterruptibly(long arg) throws InterruptedException {
        //创建一个独占锁节点入队
        final Node node = addWaiter(Node.EXCLUSIVE);
        //抢锁是否失败
        boolean failed = true;
        try {
            for (; ; ) {
                //获取当前节点的前驱节点
                final Node p = node.predecessor();
                //前驱节点是头节点 && 尝试争抢锁成功
                if (p == head && tryAcquire(arg)) {
                    //帮助老的头节点出队
                    setHead(node);
                    p.next = null; // help GC
                    failed = false;
                    return;
                }
                //走到这里说明又白忙活了，，，没拿到锁，，或者当前节点的前驱节点不是头节点
                //这个时候要判断下当前节点争抢锁失败了要不要park，如果要park，在park掉当前节点的线程，
                //如果当前节点的线程还没有拿到锁之前，被其他线程设置中断信号
                //如果有的话就抛出中断异常
                if (shouldParkAfterFailedAcquire(p, node) &&
                        parkAndCheckInterrupt())
                    throw new InterruptedException();
            }
        } finally {
            //抛出中断异常以后，就要走取消抢锁的逻辑...
            if (failed)
                cancelAcquire(node);
        }
    }

    //==================================以上为独占锁的主要逻辑==========================================//


    //==================================以下为条件队列的主要逻辑==========================================//

    //又是一个队列
    public class ConditionObject implements Condition, java.io.Serializable {

        private static final long serialVersionUID = 1173984872572414699L;
        //第一个等待锁的节点
        private transient Node firstWaiter;
        //最后一个等待锁的节点
        private transient Node lastWaiter;

        public ConditionObject() {
        }

        //等待
        public final void await() throws InterruptedException {
            //如果当前线程已经被挂起，直接抛出中断异常
            if (Thread.interrupted())
                throw new InterruptedException();
            //将当前线程封装成节点加入到条件队列
            Node node = addConditionWaiter();
            //释放线程的全部锁资源
            //为什么这里要释放掉全部的锁？
            //如果此时线程不释放锁资源，其他线程没办法拿到锁触发当前线程的唤醒机制
            long savedState = fullyRelease(node);
            //中断状态：
            //-1:当前线程在条件队列接收到了中断信号
            //0:当前线程在条件队列没有接收到中断信号
            //1:当前线程在条件队列没有接受到中断信号，但是在阻塞队列接收到了中断信号
            int interruptMode = 0;
            //如果当前线程不在阻塞队列
            while (!isOnSyncQueue(node)) {
                //挂起当前线程
                LockSupport.park(this);
                //判断当前线程在等待期间是否被中断过，无论是否发生中断，最终都会进入到阻塞队列
                //什么时候会被唤醒？都有几种情况？
                //1.常规：外部线程获取到lock之后，调用了signal方法，转移条件队列的头节点到阻塞队列，当这个节点获取到锁之后，会唤醒
                //2.转移至阻塞队列后，发现阻塞队列的前驱节点状态是取消状态，此时会唤醒当前节点
                //3.当前节点挂起期间，被外部线程使用中断唤醒...
                if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
                    break;
            }
            //来到这里说明当前线程已经被其他线程调用了signal方法，加入到了阻塞队列
            //如果当前线程在竞争锁的过程中被中断过 && 中断标识位不是 throw_ie
            if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
                //将当前线程的中断标识位设置为重新中断
                interruptMode = REINTERRUPT;

            if (node.nextWaiter != null)
                //做一次全队列的垃圾节点清理
                unlinkCancelledWaiters();
            if (interruptMode != 0)
                //在wait之后报告响应中断
                reportInterruptAfterWait(interruptMode);
        }

        //将当前节点添加到条件队列挂起
        private Node addConditionWaiter() {
            //获取尾结点的引用
            Node t = lastWaiter;
            //条件一：尾结点！=空
            //条件二：尾结点的状态！=-2，说明被中断了
            if (t != null && t.waitStatus != Node.CONDITION) {
                //做一次全队列的垃圾节点清理
                unlinkCancelledWaiters();
                //重新获取尾结点的引用，因为在刚才的清理中，尾结点可能换成新的了
                t = lastWaiter;
            }
            //封装成node
            Node node = new Node(Thread.currentThread(), Node.CONDITION);
            //如果尾结点为空，说明队列为空，当前节点是进入队列的第一个元素
            if (t == null)
                firstWaiter = node;
                //队列不为空
            else
                t.nextWaiter = node;
            lastWaiter = node;
            //返回当前线程封装成的节点
            return node;
        }

        //唤醒
        public final void signal() {
            //判断当前线程是不是持有的独占锁，如果不是，直接抛出异常
            if (!isHeldExclusively())
                throw new IllegalMonitorStateException();
            //获取条件队列的首节点
            Node first = firstWaiter;
            //如果首节点不为空
            if (first != null)
                doSignal(first);//唤醒条件队列的首节点线程
        }

        private void doSignal(Node first) {

            do {
                //当前first马上要出队了，所以更新firstWaiter为当前节点的下一个节点
                //如果当前节点的下一个节点是null，说明条件队列只有当前一个节点了...当前出队后，整个队列就空了
                //所以需要更新lastWaiter==null
                if ((firstWaiter = first.nextWaiter) == null) lastWaiter = null;
                //当前节点即将出队列，断开和下一个节点的关系
                first.nextWaiter = null;
                /*
                 * transferForSignal(first) 返回true 当前first节点迁移到阻塞队列成功 false 迁移失败
                 * while循环：(first =firstWaiter)!=null 当前first 迁移失败 ，则将first更新为first.next 继续尝试迁移
                 * 直至迁移某个节点成功，或者条件队列为 null 为止。
                 */
            } while (!transferForSignal(first) && (first = firstWaiter) != null);
        }

        private void reportInterruptAfterWait(int interruptMode)
                throws InterruptedException {
            if (interruptMode == THROW_IE)
                throw new InterruptedException();
            else if (interruptMode == REINTERRUPT)
                selfInterrupt();
        }


        private void unlinkCancelledWaiters() {
            Node t = firstWaiter;
            Node trail = null;
            while (t != null) {
                Node next = t.nextWaiter;
                if (t.waitStatus != Node.CONDITION) {
                    t.nextWaiter = null;
                    if (trail == null)
                        firstWaiter = next;
                    else
                        trail.nextWaiter = next;
                    if (next == null)
                        lastWaiter = trail;
                } else
                    trail = t;
                t = next;
            }
        }

        private int checkInterruptWhileWaiting(Node node) {
            return Thread.interrupted() ?
                    (transferAfterCancelledWait(node) ? THROW_IE : REINTERRUPT) :
                    0;
        }


        private void doSignalAll(Node first) {
            lastWaiter = firstWaiter = null;
            do {
                Node next = first.nextWaiter;
                first.nextWaiter = null;
                transferForSignal(first);
                first = next;
            } while (first != null);
        }


        // public methods


        public final void signalAll() {
            if (!isHeldExclusively())
                throw new IllegalMonitorStateException();
            Node first = firstWaiter;
            if (first != null)
                doSignalAll(first);
        }

        public final void awaitUninterruptibly() {
            Node node = addConditionWaiter();
            long savedState = fullyRelease(node);
            boolean interrupted = false;
            while (!isOnSyncQueue(node)) {
                LockSupport.park(this);
                if (Thread.interrupted())
                    interrupted = true;
            }
            if (acquireQueued(node, savedState) || interrupted)
                selfInterrupt();
        }


        private static final int REINTERRUPT = 1;
        private static final int THROW_IE = -1;


        public final long awaitNanos(long nanosTimeout)
                throws InterruptedException {
            if (Thread.interrupted())
                throw new InterruptedException();
            Node node = addConditionWaiter();
            long savedState = fullyRelease(node);
            final long deadline = System.nanoTime() + nanosTimeout;
            int interruptMode = 0;
            while (!isOnSyncQueue(node)) {
                if (nanosTimeout <= 0L) {
                    transferAfterCancelledWait(node);
                    break;
                }
                if (nanosTimeout >= spinForTimeoutThreshold)
                    LockSupport.parkNanos(this, nanosTimeout);
                if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
                    break;
                nanosTimeout = deadline - System.nanoTime();
            }
            if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
                interruptMode = REINTERRUPT;
            if (node.nextWaiter != null)
                unlinkCancelledWaiters();
            if (interruptMode != 0)
                reportInterruptAfterWait(interruptMode);
            return deadline - System.nanoTime();
        }

        public final boolean awaitUntil(Date deadline)
                throws InterruptedException {
            long abstime = deadline.getTime();
            if (Thread.interrupted())
                throw new InterruptedException();
            Node node = addConditionWaiter();
            long savedState = fullyRelease(node);
            boolean timedout = false;
            int interruptMode = 0;
            while (!isOnSyncQueue(node)) {
                if (System.currentTimeMillis() > abstime) {
                    timedout = transferAfterCancelledWait(node);
                    break;
                }
                LockSupport.parkUntil(this, abstime);
                if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
                    break;
            }
            if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
                interruptMode = REINTERRUPT;
            if (node.nextWaiter != null)
                unlinkCancelledWaiters();
            if (interruptMode != 0)
                reportInterruptAfterWait(interruptMode);
            return !timedout;
        }

        public final boolean await(long time, TimeUnit unit)
                throws InterruptedException {
            long nanosTimeout = unit.toNanos(time);
            if (Thread.interrupted())
                throw new InterruptedException();
            Node node = addConditionWaiter();
            long savedState = fullyRelease(node);
            final long deadline = System.nanoTime() + nanosTimeout;
            boolean timedout = false;
            int interruptMode = 0;
            while (!isOnSyncQueue(node)) {
                if (nanosTimeout <= 0L) {
                    timedout = transferAfterCancelledWait(node);
                    break;
                }
                if (nanosTimeout >= spinForTimeoutThreshold)
                    LockSupport.parkNanos(this, nanosTimeout);
                if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
                    break;
                nanosTimeout = deadline - System.nanoTime();
            }
            if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
                interruptMode = REINTERRUPT;
            if (node.nextWaiter != null)
                unlinkCancelledWaiters();
            if (interruptMode != 0)
                reportInterruptAfterWait(interruptMode);
            return !timedout;
        }

        //  support for instrumentation

        final boolean isOwnedBy(AbstractQueuedLongSynchronizer sync) {
            return sync == AbstractQueuedLongSynchronizer.this;
        }

        protected final boolean hasWaiters() {
            if (!isHeldExclusively())
                throw new IllegalMonitorStateException();
            for (Node w = firstWaiter; w != null; w = w.nextWaiter) {
                if (w.waitStatus == Node.CONDITION)
                    return true;
            }
            return false;
        }

        protected final int getWaitQueueLength() {
            if (!isHeldExclusively())
                throw new IllegalMonitorStateException();
            int n = 0;
            for (Node w = firstWaiter; w != null; w = w.nextWaiter) {
                if (w.waitStatus == Node.CONDITION)
                    ++n;
            }
            return n;
        }

        protected final Collection<Thread> getWaitingThreads() {
            if (!isHeldExclusively())
                throw new IllegalMonitorStateException();
            ArrayList<Thread> list = new ArrayList<Thread>();
            for (Node w = firstWaiter; w != null; w = w.nextWaiter) {
                if (w.waitStatus == Node.CONDITION) {
                    Thread t = w.thread;
                    if (t != null)
                        list.add(t);
                }
            }
            return list;
        }
    }

    //释放线程的全部锁资源
    final long fullyRelease(Node node) {
        /*
         * 完全释放锁是否成功
         * 当failed失败的时候，说明当前线程是未持有锁调用 await 方法的线程... 错误写法
         * 假设失败，在finally代码块中 会将刚刚加入到条件队列的 当前线程对应的node状态 修改为 取消状态
         * 后继线程就会将取消状态的节点给清理出去...
         */
        boolean failed = true;
        try {
            //获取当前线程持有的state值总数
            long savedState = getState();
            //绝大部分情况下：release这里会返回true
            if (release(savedState)) {
                //失败标记设置为false
                failed = false;
                /*
                 * 返回当前线程释放的state值
                 * 为什么要返回？
                 * 因为当节点被迁移到阻塞队列以后，再次被唤醒，且当前node在阻塞队列中是head.next 而且
                 * 当前lock状态是state=0 的情况下 当前node 可以获取到锁 此时需要将state 设置为 savedState
                 */
                return savedState;
            } else {
                throw new IllegalMonitorStateException();
            }
        } finally {
            //如果失败了，就把当前节点状态改成取消
            if (failed)
                node.waitStatus = Node.CANCELLED;
        }
    }

    //判断指定节点是否在阻塞队列
    final boolean isOnSyncQueue(Node node) {
        /*
         * 条件1：node.waitStatus==node.condition
         * 条件成立说明当前node一定是在条件队列，因为signal方法迁移节点到阻塞队列前，会将node的状态设置为0
         * 条件2：前置条件：node.waitStatus ！= Node.CONDITION ====>
         * node.waitStatus ==0 : 表示当前节点已经被signal
         * node.waitStatus ==1 : 当前线程是未持有锁调用await  最终这个节点将被取消
         * node.waitStatus ==0 为什么还要判断 node.prev == null ？
         * 因为signal方法是先修改状态在迁移
         */
        if (node.waitStatus == Node.CONDITION || node.prev == null)
            return false;
        /*
         * 执行到这里，
         * node.waitStatus !=Condition 且 node.prev!=null ====> 可以排除掉 node.waitStatus ==1 取消状态
         * 为什么可以排除掉取消状态？因为signal方法是不会吧取消状态的节点迁移走的
         * 设置prev引用的逻辑是迁移阻塞队列 逻辑的设置的 eng方法
         * 入队的逻辑：1.设置node.prev =tail
         * 2.cas当前node为 阻塞队列的tail节点成功才算是真正的进入到阻塞队列
         * 可以推算出，就算是prev不是null，也不能说明当前node已经成功入队到阻塞队列了。
         */
        if (node.next != null)
            return true;
        //执行到这里从阻塞队列的尾巴开始向前遍历查找node，找到了就返回true，找不到返回false，
        //当前node有可能正在迁移中，还未完成。
        return findNodeFromTail(node);
    }


    //从尾向前找节点
    private boolean findNodeFromTail(Node node) {
        Node t = tail;
        for (; ; ) {
            if (t == node)
                return true;
            if (t == null)
                return false;
            t = t.prev;
        }
    }

    final boolean transferAfterCancelledWait(Node node) {
        //使用 cas 修改节点状态，如果还能修改成功，说明线程被中断时，signal 还没有被调用。
        // 这里有一个知识点，就是线程被唤醒，并不一定是在 java 层面执行了locksupport.unpark，也可能是调用了线程的 interrupt()方法，这个方法会更新一个中断标识，并且会唤醒处于阻塞状态下的线程。
        if (compareAndSetWaitStatus(node, Node.CONDITION, 0)) {
            enq(node);//如果 cas 成功，则把node 添加到 AQS 队列
            return true;
        }
        // 如果 cas 失败，则判断当前 node 是否已经在 AQS 队列上，如果不在，则让给其他线程执行
        // 当 node 被触发了 signal 方法时， node 就会被加到 aqs 队列上
        while (!isOnSyncQueue(node))//循环检测 node 是否已经成功添加到 AQS 队列中。如果没有，则通过 yield
            Thread.yield();//使当前线程由执行状态，变成为就绪状态，让出cpu时间，在下一个线程执行时候，此线程有可能被执行，也有可能没有被执行。
        return false;
    }

    //接收到signal信号后，把节点转入等待队列
    final boolean transferForSignal(Node node) {
        /*
         * cas修改当前节点的状态，修改为0，因为当前节点马上要迁移到阻塞队列了
         * 成功：当前节点在条件队列中状态正常
         * 失败：
         *      1.取消状态 （线程await时，未持有锁，最终线程对应的node将会被设置为取消状态）
         *      2.node对应的线程 挂起期间，被其他线程使用中断信号唤醒过...（就会主动进入到阻塞队列，这时
         *      也会修改状态为0）
         */
        if (!compareAndSetWaitStatus(node, Node.CONDITION, 0))
            return false;
        //添加节点到等待队列，并返回节点的前继节点(prev)
        Node p = enq(node);
        //ws:前驱节点的状态
        int ws = p.waitStatus;
        /*
         * 条件1：ws>0成立：说明前驱节点的状态在阻塞队列中是取消状态，唤醒当前节点
         * 条件2：前置条件 ws<=0
         * cas 返回true表示设置前驱节点状态为signal状态成功
         * cas返回false，什么时候返回false？
         * 当前驱node对应的线程是lockInterrupt入队的node时，是会响应中断的，外部线程给前驱线程中断信号之后
         * 前驱node会将状态修改为 取消状态，并且执行出队逻辑...
         * 前驱节点状态只要不是0 或者 -1 ，那么就唤醒当前线程
         */
        if (ws > 0 || !compareAndSetWaitStatus(p, ws, Node.SIGNAL))
            //如果前节点被取消，说明当前为最后一个等待线程，unpark唤醒当前线程
            LockSupport.unpark(node.thread);
        //如果 node 的 prev 节点已经是signal 状态，那么被阻塞的 ThreadA 的唤醒工作由 AQS 队列来完成
        return true;
    }

    //=============================================以下为条件队列的主要逻辑==============================================================//


    private void doReleaseShared() {
        //自旋
        for (; ; ) {
            //获取头节点的引用
            Node h = head;
            //如果头节点不为空 && 头节点不等于尾结点
            //说明此时，头结点还没有被刚刚唤醒的线程占用
            if (h != null && h != tail) {
                int ws = h.waitStatus;
                //如果头结点的转态=-1
                if (ws == Node.SIGNAL) {
                    //cas设置头节点的状态失败
                    if (!compareAndSetWaitStatus(h, Node.SIGNAL, 0))
                        continue;
                    //cas成功，唤醒头节点
                    unparkSuccessor(h);
                }
                //这个 CAS 失败的场景是：执行到这里的时候，刚好有一个节点入队，入队会将这个 ws 设置为 -1
                else if (ws == 0 &&
                        !compareAndSetWaitStatus(h, 0, Node.PROPAGATE))
                    continue;
            }
            //如果到这里的时候，前面唤醒的线程已经占领了 head，那么再循环
            //通过检查头节点是否改变了，如果改变了就继续循环
            if (h == head)
                break;
        }
    }

    private void setHeadAndPropagate(Node node, long propagate) {
        Node h = head; // Record old head for check below
        setHead(node);

        if (propagate > 0 || h == null || h.waitStatus < 0 ||
            (h = head) == null || h.waitStatus < 0) {
            Node s = node.next;
            if (s == null || s.isShared())
                doReleaseShared();
        }
    }



    private boolean doAcquireNanos(long arg, long nanosTimeout)
            throws InterruptedException {
        if (nanosTimeout <= 0L)
            return false;
        final long deadline = System.nanoTime() + nanosTimeout;
        final Node node = addWaiter(Node.EXCLUSIVE);
        boolean failed = true;
        try {
            for (;;) {
                final Node p = node.predecessor();
                if (p == head && tryAcquire(arg)) {
                    setHead(node);
                    p.next = null; // help GC
                    failed = false;
                    return true;
                }
                nanosTimeout = deadline - System.nanoTime();
                if (nanosTimeout <= 0L)
                    return false;
                if (shouldParkAfterFailedAcquire(p, node) &&
                    nanosTimeout > spinForTimeoutThreshold)
                    LockSupport.parkNanos(this, nanosTimeout);
                if (Thread.interrupted())
                    throw new InterruptedException();
            }
        } finally {
            if (failed)
                cancelAcquire(node);
        }
    }

    private void doAcquireShared(long arg) {
        final Node node = addWaiter(Node.SHARED);
        boolean failed = true;
        try {
            boolean interrupted = false;
            for (;;) {
                final Node p = node.predecessor();
                if (p == head) {
                    long r = tryAcquireShared(arg);
                    if (r >= 0) {
                        setHeadAndPropagate(node, r);
                        p.next = null; // help GC
                        if (interrupted)
                            selfInterrupt();
                        failed = false;
                        return;
                    }
                }
                if (shouldParkAfterFailedAcquire(p, node) &&
                    parkAndCheckInterrupt())
                    interrupted = true;
            }
        } finally {
            if (failed)
                cancelAcquire(node);
        }
    }



    private boolean doAcquireSharedNanos(long arg, long nanosTimeout)
            throws InterruptedException {
        if (nanosTimeout <= 0L)
            return false;
        final long deadline = System.nanoTime() + nanosTimeout;
        final Node node = addWaiter(Node.SHARED);
        boolean failed = true;
        try {
            for (;;) {
                final Node p = node.predecessor();
                if (p == head) {
                    long r = tryAcquireShared(arg);
                    if (r >= 0) {
                        setHeadAndPropagate(node, r);
                        p.next = null; // help GC
                        failed = false;
                        return true;
                    }
                }
                nanosTimeout = deadline - System.nanoTime();
                if (nanosTimeout <= 0L)
                    return false;
                if (shouldParkAfterFailedAcquire(p, node) &&
                    nanosTimeout > spinForTimeoutThreshold)
                    LockSupport.parkNanos(this, nanosTimeout);
                if (Thread.interrupted())
                    throw new InterruptedException();
            }
        } finally {
            if (failed)
                cancelAcquire(node);
        }
    }

    // Main exported methods


    public final void acquireShared(long arg) {
        if (tryAcquireShared(arg) < 0)
            doAcquireShared(arg);
    }

    public final void acquireSharedInterruptibly(long arg) throws InterruptedException {
        //如果当前线程被中断，抛出中断异常
        if (Thread.interrupted())
            throw new InterruptedException();
        //当前线程尝试获取共享锁，state<0，说明当前线程需要加入到共享锁队列
        if (tryAcquireShared(arg) < 0)
            //将当前线程加入到共享锁队列
            doAcquireSharedInterruptibly(arg);
    }

    private void doAcquireSharedInterruptibly(long arg)
            throws InterruptedException {
        //将当前线程封装成节点入队，共享节点，使用的是state的高16位运算
        final Node node = addWaiter(Node.SHARED);
        boolean failed = true;
        try {
            //自旋
            for (; ; ) {
                //获取当前节点的前驱
                final Node p = node.predecessor();
                //如果前驱节点是头节点
                if (p == head) {
                    //当前节点就可以尝试去抢锁
                    long r = tryAcquireShared(arg);
                    //此时说明抢到锁了
                    if (r >= 0) {
                        //修改头节点的值
                        setHeadAndPropagate(node, r);
                        //头节点出队
                        p.next = null; // help GC
                        //代表抢锁成功
                        failed = false;
                        return;
                    }
                }
                //否则的话，线程在这里park，如果线程中断信号=true，就会抛出中断异常
                if (shouldParkAfterFailedAcquire(p, node) &&
                        parkAndCheckInterrupt())
                    throw new InterruptedException();
            }
        } finally {
            //如果抢锁失败了，就走取消竞争锁的逻辑
            if (failed)
                cancelAcquire(node);
        }
    }


    public final boolean tryAcquireSharedNanos(long arg, long nanosTimeout)
            throws InterruptedException {
        if (Thread.interrupted())
            throw new InterruptedException();
        return tryAcquireShared(arg) >= 0 ||
                doAcquireSharedNanos(arg, nanosTimeout);
    }

    public final boolean releaseShared(long arg) {
        if (tryReleaseShared(arg)) {
            doReleaseShared();
            return true;
        }
        return false;
    }

    // Queue inspection methods

    public final boolean hasQueuedThreads() {
        return head != tail;
    }

    public final boolean hasContended() {
        return head != null;
    }

    public final Thread getFirstQueuedThread() {
        // handle only fast path, else relay
        return (head == tail) ? null : fullGetFirstQueuedThread();
    }

    private Thread fullGetFirstQueuedThread() {

        Node h, s;
        Thread st;
        if (((h = head) != null && (s = h.next) != null &&
             s.prev == head && (st = s.thread) != null) ||
            ((h = head) != null && (s = h.next) != null &&
             s.prev == head && (st = s.thread) != null))
            return st;


        Node t = tail;
        Thread firstThread = null;
        while (t != null && t != head) {
            Thread tt = t.thread;
            if (tt != null)
                firstThread = tt;
            t = t.prev;
        }
        return firstThread;
    }

    public final boolean isQueued(Thread thread) {
        if (thread == null)
            throw new NullPointerException();
        for (Node p = tail; p != null; p = p.prev)
            if (p.thread == thread)
                return true;
        return false;
    }

    final boolean apparentlyFirstQueuedIsExclusive() {
        Node h, s;
        return (h = head) != null &&
            (s = h.next)  != null &&
            !s.isShared()         &&
            s.thread != null;
    }

    //判断能当前线程是否还有前驱节点
    public final boolean hasQueuedPredecessors() {
        //尾结点
        Node t = tail; // Read fields in reverse initialization order
        //头节点
        Node h = head;
        Node s;
        //头节点不等于尾结点  && (头节点的下一个节点是空 || 头节点的下一个节点的线程不是当前线程)
        //返回true的话，也就是说当前阻塞队列存在，并且有等待去获取锁的线程。
        return h != t &&
                ((s = h.next) == null || s.thread != Thread.currentThread());
    }


    // Instrumentation and monitoring methods

    public final int getQueueLength() {
        int n = 0;
        for (Node p = tail; p != null; p = p.prev) {
            if (p.thread != null)
                ++n;
        }
        return n;
    }

    public final Collection<Thread> getQueuedThreads() {
        ArrayList<Thread> list = new ArrayList<Thread>();
        for (Node p = tail; p != null; p = p.prev) {
            Thread t = p.thread;
            if (t != null)
                list.add(t);
        }
        return list;
    }

    public final Collection<Thread> getExclusiveQueuedThreads() {
        ArrayList<Thread> list = new ArrayList<Thread>();
        for (Node p = tail; p != null; p = p.prev) {
            if (!p.isShared()) {
                Thread t = p.thread;
                if (t != null)
                    list.add(t);
            }
        }
        return list;
    }

    public final Collection<Thread> getSharedQueuedThreads() {
        ArrayList<Thread> list = new ArrayList<Thread>();
        for (Node p = tail; p != null; p = p.prev) {
            if (p.isShared()) {
                Thread t = p.thread;
                if (t != null)
                    list.add(t);
            }
        }
        return list;
    }


    // Internal support methods for Conditions



    // Instrumentation methods for conditions

    public final boolean owns(ConditionObject condition) {
        return condition.isOwnedBy(this);
    }

    public final boolean hasWaiters(ConditionObject condition) {
        if (!owns(condition))
            throw new IllegalArgumentException("Not owner");
        return condition.hasWaiters();
    }

    public final int getWaitQueueLength(ConditionObject condition) {
        if (!owns(condition))
            throw new IllegalArgumentException("Not owner");
        return condition.getWaitQueueLength();
    }

    public final Collection<Thread> getWaitingThreads(ConditionObject condition) {
        if (!owns(condition))
            throw new IllegalArgumentException("Not owner");
        return condition.getWaitingThreads();
    }


    //往下都是模板模式的体现，具体的尝试获取锁的逻辑需要在业务类里面重写去实现。
    protected boolean tryAcquire(long arg) {
        throw new UnsupportedOperationException();
    }

    protected boolean tryRelease(long arg) {
        throw new UnsupportedOperationException();
    }

    protected long tryAcquireShared(long arg) {
        throw new UnsupportedOperationException();
    }

    protected boolean tryReleaseShared(long arg) {
        throw new UnsupportedOperationException();
    }

    //判断当前线程是不是独占锁
    protected boolean isHeldExclusively() {
        throw new UnsupportedOperationException();
    }


    public final boolean tryAcquireNanos(long arg, long nanosTimeout)
            throws InterruptedException {
        if (Thread.interrupted())
            throw new InterruptedException();
        return tryAcquire(arg) ||
                doAcquireNanos(arg, nanosTimeout);
    }

}
